package ext;

import java.util.*;
import org.junit.*;

public class CycleDependency {
    
    //[['A', 'B'], ['B', 'C'], ['C', 'D'], ['B', 'D']] => false
    public boolean hasCycle(char[][] cs) {

        Set<Character> all = new HashSet<>();
        Set<Character> no = new HashSet<>();
        Map<Character, List<Character>> map = new HashMap<>();
        Map<Character, Integer> nexts = new HashMap<>();

        for (char[] c: cs) {
            all.add(c[0]);
            all.add(c[1]);
            no.add(c[1]);
            nexts.put(c[1], nexts.getOrDefault(c[1], 0) + 1);
            if (map.containsKey(c[0])) {
                map.get(c[0]).add(c[1]);
            } else {
                List<Character> list = new ArrayList<>();
                list.add(c[1]);
                map.put(c[0], list);
            }
        }
        Queue<Character> queue = new LinkedList<>();
        for (char c: all) {
            if (!no.contains(c)) {
                queue.offer(c);
            }
        }

        while (!queue.isEmpty()) {
            int n = queue.size();
            for (int i = 0; i < n; i++) {
                char c = queue.poll();
                all.remove(c);
                List<Character> list = map.get(c);
                if (list != null) {

                    list.forEach(e -> {
                        int t = nexts.get(e);
                        if (t == 1) {
                            queue.offer(e);
                            nexts.remove(e);
                        } else {
                            nexts.put(e, t - 1);
                        }
                    });

                }
            }
        }
        return !all.isEmpty();
    }

    @Test
    public void test() {
        //['A', 'B'], ['B', 'C'], ['C', 'D'], ['B', 'D']
        char[][] cs = {new char[]{'A', 'B'}, new char[]{'B', 'C'}, new char[]{'C', 'A'}}; //, new char[]{'B', 'D'}
        System.out.println(hasCycle(cs));
    }
}
